


class Sort:
    def __init__(self,is_up,list):
        self.is_up :bool =is_up
        self.list  = list

    #冒泡排序
    def bubble_sort(self):
        exchange = False
        if self.is_up:
            for round in range(len(self.list)-1):
                exchange = False
                for i in range(len(self.list)-round-1):
                    if self.list[i]>self.list[i+1]:
                        self.list[i],self.list[i+1]=self.list[i+1],self.list[i]
                        exchange=True
                    else:
                        continue
                if not exchange:
                    break
        else:
            for round in range(len(self.list)-1):
                exchange = False
                for i in range(len(self.list)-round-1):
                    if self.list[i]<self.list[i+1]:
                        self.list[i],self.list[i+1]=self.list[i+1],self.list[i]
                        exchange = True
                if not exchange:
                    break
        print(self.list)

    #选择排序
    def selection_sort(self):
        for round in range(len(self.list)-1):
            min_loc = round
            for i in range(round+1,len(self.list)):

                if self.list[i]>self.list[min_loc] and self.is_up:
                    self.list[i],self.list[min_loc]=self.list[min_loc],self.list[i]
                elif self.list[i]<self.list[min_loc] and not self.is_up:
                    self.list[i],self.list[min_loc]=self.list[min_loc],self.list[i]
        return self.list

    #插入排序
    def insertion_sort(self):

        for i in range(1 ,len(self.list)):
            temp = 0
            j = 0
            if self.is_up:
                while self.list[i]>self.list[temp] and temp<i+1:
                    temp+=1

            else:
                while self.list[i]<self.list[temp] and temp<i+1:
                    temp+=1
            self.list.insert(temp, self.list[i])
            self.list.pop(i + 1)
        return self.list

    #快速排序
    def quick_sort(self):
        #完成一个递归函数，取一个数，当左右指针重合停止
        def partition(left,right):#n  11 !! 23  24 83 14 20     71
            temp  = self.list[left]
            while left < right:
                while  left < right and self.list[right] >=temp:
                    right -= 1
                self.list[left]  =  self.list[right]
                while  left < right and self.list[left]<=temp:
                    left += 1
                self.list[right] = self.list[left]
            self.list[left] = temp
            return left

        def quick_sort(left,right):
            if left < right:
                mid = partition(left,right)
                partition(mid+1,right)
                partition(left,mid-1)

        quick_sort(0,len(self.list)-1)
        return self.list

    def heap_sort(self):
        #双指针用于标记堆的上下层关系，用temp记录移动的量
        def shift(high,low):
            i = low
            j = i*i +1
            temp  =  low
            while j<high:
                if self.list[j]<self.list[j+1]:
                    j = j+1
                self.list[j] = temp
                if self.list[j]< temp:
                    self.list[i] = temp
                i = j
                j = i*i +1


#w未完成



if __name__ == '__main__':
    sort = Sort(is_up=False,list=[34, 15, 88, 21, 42, 56, 77, 93, 65,34, 10])
    print(sort.heap_sort())

















